Enterprise customers are increasingly adopting MPLS-based VPN services to implement a communication network among their respective customer sites via a service provider's network. Such MPLS-based VPNs provide direct any-to-any reachability among an enterprise's customer sites. Enterprise customers may, for example, deploy VoIP services to their customer sites via their respective VPNs. Traditionally, cross-VPN communication sessions (such as a VoIP communication session between VoIP devices associated with different VPNs) are established via communication links that are implemented outside of and/or separate from the MPLS-based network that implements the VPNs.